#include<bits/stdc++.h>
using namespace std;
/*class Solution {
public:
    vector<string> partitionString(string s) {
        vector<string> ans;
        unordered_set<string> hash;
        string t="";
        for(char ch:s)
        {
            t+=ch;
            if(hash.insert(t).second)
            {
                ans.push_back(t);
                t.clear();
            }
        }
        return ans;
    }
};*/
struct node
{
    node* childs[26]={};
};

class Solution {
public:
    vector<string> partitionString(string s) {
        vector<string> ans;
        node* root=new node();
        node* cur=root;
        int left=0;
        for(int i=0;i<s.size();i++)
        {
            char ch=s[i]-'a';
            if(cur->childs[ch]==nullptr)
            {
                cur->childs[ch]=new node();
                ans.push_back(s.substr(left,i-left+1));
                left=i+1;
                cur=root;
            }
            else cur=cur->childs[ch];
        
        }
        return ans;
    }
};